home *** CD-ROM | disk | FTP | other *** search
/ Developer CD Series 1995 August: Tool Chest / Dev.CD Aug 95 TC / Dev.CD Aug 95 TC.toast / Tool Chest / Development Tools & Languages / Dylan Related / Marlais / Marlais 0.5.9-portable sources / gc / alloc.c < prev    next >
Encoding:
C/C++ Source or Header  |  1995-03-15  |  21.4 KB  |  734 lines  |  [TEXT/ttxt]
  1. /*
  2.  * Copyright 1988, 1989 Hans-J. Boehm, Alan J. Demers
  3.  * Copyright (c) 1991-1994 by Xerox Corporation.  All rights reserved.
  4.  *
  5.  * THIS MATERIAL IS PROVIDED AS IS, WITH ABSOLUTELY NO WARRANTY EXPRESSED
  6.  * OR IMPLIED.  ANY USE IS AT YOUR OWN RISK.
  7.  *
  8.  * Permission is hereby granted to use or copy this program
  9.  * for any purpose,  provided the above notices are retained on all copies.
  10.  * Permission to modify the code and to distribute modified code is granted,
  11.  * provided the above notices are retained, and a notice that the code was
  12.  * modified is included with the above copyright notice.
  13.  *
  14.  */
  15. /* Boehm, February 10, 1995 1:18 pm PST */
  16.  
  17.  
  18. # include "gc_priv.h"
  19.  
  20. # include <stdio.h>
  21. # ifndef MACOS
  22. #   include <signal.h>
  23. #   include <sys/types.h>
  24. # endif
  25.  
  26. /*
  27.  * Separate free lists are maintained for different sized objects
  28.  * up to MAXOBJSZ.
  29.  * The call GC_allocobj(i,k) ensures that the freelist for
  30.  * kind k objects of size i points to a non-empty
  31.  * free list. It returns a pointer to the first entry on the free list.
  32.  * In a single-threaded world, GC_allocobj may be called to allocate
  33.  * an object of (small) size i as follows:
  34.  *
  35.  *            opp = &(GC_objfreelist[i]);
  36.  *            if (*opp == 0) GC_allocobj(i, NORMAL);
  37.  *            ptr = *opp;
  38.  *            *opp = obj_link(ptr);
  39.  *
  40.  * Note that this is very fast if the free list is non-empty; it should
  41.  * only involve the execution of 4 or 5 simple instructions.
  42.  * All composite objects on freelists are cleared, except for
  43.  * their first word.
  44.  */
  45.  
  46. /*
  47.  *  The allocator uses GC_allochblk to allocate large chunks of objects.
  48.  * These chunks all start on addresses which are multiples of
  49.  * HBLKSZ.   Each allocated chunk has an associated header,
  50.  * which can be located quickly based on the address of the chunk.
  51.  * (See headers.c for details.) 
  52.  * This makes it possible to check quickly whether an
  53.  * arbitrary address corresponds to an object administered by the
  54.  * allocator.
  55.  */
  56.  
  57. word GC_non_gc_bytes = 0;  /* Number of bytes not intended to be collected */
  58.  
  59. word GC_gc_no = 0;
  60.  
  61. int GC_incremental = 0;    /* By default, stop the world.    */
  62.  
  63. int GC_full_freq = 4;       /* Every 5th collection is a full    */
  64.                /* collection.            */
  65.  
  66. char * GC_copyright[] =
  67. {"Copyright 1988,1989 Hans-J. Boehm and Alan J. Demers",
  68. "Copyright (c) 1991-1995 by Xerox Corporation.  All rights reserved.",
  69. "THIS MATERIAL IS PROVIDED AS IS, WITH ABSOLUTELY NO WARRANTY",
  70. " EXPRESSED OR IMPLIED.  ANY USE IS AT YOUR OWN RISK."};
  71.  
  72.  
  73. /* some more variables */
  74.  
  75. extern signed_word GC_mem_found;  /* Number of reclaimed longwords    */
  76.                   /* after garbage collection          */
  77.  
  78. bool GC_dont_expand = 0;
  79.  
  80. word GC_free_space_divisor = 4;
  81.  
  82. int GC_never_stop_func(NO_PARAMS) { return(0); }
  83.  
  84. CLOCK_TYPE GC_start_time;
  85.  
  86. int GC_timeout_stop_func(NO_PARAMS)
  87. {
  88.     CLOCK_TYPE current_time;
  89.     static unsigned count = 0;
  90.     unsigned long time_diff;
  91.     
  92.     if ((count++ & 3) != 0) return(0);
  93.     GET_TIME(current_time);
  94.     time_diff = MS_TIME_DIFF(current_time,GC_start_time);
  95.     if (time_diff >= TIME_LIMIT) {
  96. #       ifdef PRINTSTATS
  97.         GC_printf0("Abandoning stopped marking after ");
  98.         GC_printf1("%lu msecs\n", (unsigned long)time_diff);
  99. #    endif
  100.         return(1);
  101.     }
  102.     return(0);
  103. }
  104.  
  105. /* Return the minimum number of words that must be allocated between    */
  106. /* collections to amortize the collection cost.                */
  107. static word min_words_allocd()
  108. {
  109.     int dummy;
  110. #   ifdef THREADS
  111.      /* We punt, for now. */
  112.      register signed_word stack_size = 10000;
  113. #   else
  114.         register signed_word stack_size = (ptr_t)(&dummy) - GC_stackbottom;
  115. #   endif
  116.     register word total_root_size;  /* includes double stack size,    */
  117.                         /* since the stack is expensive    */
  118.                         /* to scan.                */
  119.     
  120.     if (stack_size < 0) stack_size = -stack_size;
  121.     total_root_size = 2 * stack_size + GC_root_size;
  122.     if (GC_incremental) {
  123.         return(BYTES_TO_WORDS(GC_heapsize + total_root_size)
  124.                / (2 * GC_free_space_divisor));
  125.     } else {
  126.         return(BYTES_TO_WORDS(GC_heapsize + total_root_size)
  127.                / GC_free_space_divisor);
  128.     }
  129. }
  130.  
  131. /* Return the number of words allocated, adjusted for explicit storage    */
  132. /* management, etc..  This number is used in deciding when to trigger    */
  133. /* collections.                                */
  134. word GC_adj_words_allocd()
  135. {
  136.     register signed_word result;
  137.     register signed_word expl_managed =
  138.             BYTES_TO_WORDS((long)GC_non_gc_bytes
  139.                     - (long)GC_non_gc_bytes_at_gc);
  140.     
  141.     /* Don't count what was explicitly freed, or newly allocated for    */
  142.     /* explicit management.  Note that deallocating an explicitly    */
  143.     /* managed object should not alter result, assuming the client    */
  144.     /* is playing by the rules.                        */
  145.     result = (signed_word)GC_words_allocd
  146.              - (signed_word)GC_mem_freed - expl_managed;
  147.     if (result > (signed_word)GC_words_allocd) result = GC_words_allocd;
  148.         /* probably client bug or unfortunate scheduling */
  149.     result += GC_words_wasted;
  150.          /* This doesn't reflect useful work.  But if there is lots of    */
  151.          /* new fragmentation, the same is probably true of the heap,    */
  152.          /* and the collection will be correspondingly cheaper.        */
  153.     if (result < (signed_word)(GC_words_allocd >> 3)) {
  154.         /* Always count at least 1/8 of the allocations.  We don't want    */
  155.         /* to collect too infrequently, since that would inhibit    */
  156.         /* coalescing of free storage blocks.                */
  157.         /* This also makes us partially robust against client bugs.    */
  158.         return(GC_words_allocd >> 3);
  159.     } else {
  160.         return(result);
  161.     }
  162. }
  163.  
  164.  
  165. /* Clear up a few frames worth of garbage left at the top of the stack.    */
  166. /* This is used to prevent us from accidentally treating garbade left    */
  167. /* on the stack by other parts of the collector as roots.  This     */
  168. /* differs from the code in misc.c, which actually tries to keep the    */
  169. /* stack clear of long-lived, client-generated garbage.            */
  170. void GC_clear_a_few_frames()
  171. {
  172. #   define NWORDS 64
  173.     word frames[NWORDS];
  174.     register int i;
  175.     
  176.     for (i = 0; i < NWORDS; i++) frames[i] = 0;
  177. }
  178.  
  179. /* Have we allocated enough to amortize a collection? */
  180. bool GC_should_collect()
  181. {
  182.     return(GC_adj_words_allocd() >= min_words_allocd());
  183. }
  184.  
  185. /* 
  186.  * Initiate a garbage collection if appropriate.
  187.  * Choose judiciously
  188.  * between partial, full, and stop-world collections.
  189.  * Assumes lock held, signals disabled.
  190.  */
  191. void GC_maybe_gc()
  192. {
  193.     static int n_partial_gcs = 0;
  194.     if (GC_should_collect()) {
  195.         if (!GC_incremental) {
  196.             GC_gcollect_inner();
  197.             n_partial_gcs = 0;
  198.         } else if (n_partial_gcs >= GC_full_freq) {
  199.             GC_initiate_full();
  200.             n_partial_gcs = 0;
  201.         } else {
  202.             /* We try to mark with the world stopped.    */
  203.             /* If we run out of time, this turns into    */
  204.             /* incremental marking.            */
  205.             GET_TIME(GC_start_time);
  206.             if (GC_stopped_mark(GC_timeout_stop_func)) {
  207. #               ifdef SAVE_CALL_CHAIN
  208.                   GC_save_callers(GC_last_stack);
  209. #               endif
  210.                 GC_finish_collection();
  211.             }
  212.             n_partial_gcs++;
  213.         }
  214.     }
  215. }
  216.  
  217.  
  218. /*
  219.  * Stop the world garbage collection.  Assumes lock held, signals disabled.
  220.  * If stop_func is not GC_never_stop_func, then abort if stop_func returns TRUE.
  221.  */
  222. bool GC_try_to_collect_inner(stop_func)
  223. GC_stop_func stop_func;
  224. {
  225. #   ifdef PRINTSTATS
  226.     GC_printf2(
  227.        "Initiating full world-stop collection %lu after %ld allocd bytes\n",
  228.        (unsigned long) GC_gc_no+1,
  229.        (long)WORDS_TO_BYTES(GC_words_allocd));
  230. #   endif
  231.     GC_promote_black_lists();
  232.     /* Make sure all blocks have been reclaimed, so sweep routines    */
  233.     /* don't see cleared mark bits.                    */
  234.     /* If we're guaranteed to finish, then this is unnecessary.        */
  235.     if (stop_func != GC_never_stop_func && !GC_reclaim_all(stop_func)) {
  236.         /* Aborted.  So far everything is still consistent.    */
  237.         return(FALSE);
  238.     }
  239.     GC_invalidate_mark_state();  /* Flush mark stack.    */
  240.     GC_clear_marks();
  241. #   ifdef SAVE_CALL_CHAIN
  242.         GC_save_callers(GC_last_stack);
  243. #   endif
  244.     if (!GC_stopped_mark(stop_func)) {
  245.         /* We're partially done and have no way to complete or use     */
  246.         /* current work.  Reestablish invariants as cheaply as        */
  247.         /* possible.                            */
  248.         GC_invalidate_mark_state();
  249.     GC_unpromote_black_lists();
  250.         if (GC_incremental) {
  251.             /* Unlikely.  But just invalidating mark state could be    */
  252.             /* expensive.                        */
  253.             GC_clear_marks();
  254.         }
  255.         return(FALSE);
  256.     }
  257.     GC_finish_collection();
  258.     return(TRUE);
  259. }
  260.  
  261.  
  262.  
  263. /*
  264.  * Perform n units of garbage collection work.  A unit is intended to touch
  265.  * roughly a GC_RATE pages.  Every once in a while, we do more than that.
  266.  */
  267. # define GC_RATE 8
  268.  
  269. int GC_deficit = 0;    /* The number of extra calls to GC_mark_some    */
  270.             /* that we have made.                */
  271.             /* Negative values are equivalent to 0.        */
  272. extern bool GC_collection_in_progress();
  273.  
  274. void GC_collect_a_little_inner(n)
  275. int n;
  276. {
  277.     register int i;
  278.     
  279.     if (GC_collection_in_progress()) {
  280.         for (i = GC_deficit; i < GC_RATE*n; i++) {
  281.             if (GC_mark_some()) {
  282.                 /* Need to finish a collection */
  283. #             ifdef SAVE_CALL_CHAIN
  284.                 GC_save_callers(GC_last_stack);
  285. #             endif
  286.         (void) GC_stopped_mark(GC_never_stop_func);
  287.                 GC_finish_collection();
  288.                 break;
  289.             }
  290.         }
  291.         if (GC_deficit > 0) GC_deficit -= GC_RATE*n;
  292.     } else {
  293.         GC_maybe_gc();
  294.     }
  295. }
  296.  
  297. int GC_collect_a_little(NO_PARAMS)
  298. {
  299.     int result;
  300.     DCL_LOCK_STATE;
  301.  
  302.     DISABLE_SIGNALS();
  303.     LOCK();
  304.     GC_collect_a_little_inner(1);
  305.     result = (int)GC_collection_in_progress();
  306.     UNLOCK();
  307.     ENABLE_SIGNALS();
  308.     return(result);
  309. }
  310.  
  311. /*
  312.  * Assumes lock is held, signals are disabled.
  313.  * We stop the world.
  314.  * If final is TRUE, then we finish the collection, no matter how long
  315.  * it takes.
  316.  * Otherwise we may fail and return FALSE if this takes too long.
  317.  * Increment GC_gc_no if we succeed.
  318.  */
  319. bool GC_stopped_mark(stop_func)
  320. GC_stop_func stop_func;
  321. {
  322.     register int i;
  323. #   ifdef PRINTSTATS
  324.     CLOCK_TYPE start_time, current_time;
  325. #   endif
  326.     
  327.     STOP_WORLD();
  328. #   ifdef PRINTSTATS
  329.     GET_TIME(start_time);
  330.     GC_printf1("--> Marking for collection %lu ",
  331.                (unsigned long) GC_gc_no + 1);
  332.     GC_printf2("after %lu allocd bytes + %lu wasted bytes\n",
  333.               (unsigned long) WORDS_TO_BYTES(GC_words_allocd),
  334.               (unsigned long) WORDS_TO_BYTES(GC_words_wasted));
  335. #   endif
  336.  
  337.     /* Mark from all roots.  */
  338.         /* Minimize junk left in my registers and on the stack */
  339.             GC_clear_a_few_frames();
  340.             GC_noop(0,0,0,0,0,0);
  341.     GC_initiate_partial();
  342.     for(i = 0;;i++) {
  343.         if ((*stop_func)()) {
  344. #               ifdef PRINTSTATS
  345.                 GC_printf0("Abandoned stopped marking after ");
  346.             GC_printf1("%lu iterations\n",
  347.                    (unsigned long)i);
  348. #            endif
  349.             GC_deficit = i; /* Give the mutator a chance. */
  350.                 START_WORLD();
  351.                 return(FALSE);
  352.         }
  353.         if (GC_mark_some()) break;
  354.     }
  355.     
  356.     GC_gc_no++;
  357. #   ifdef PRINTSTATS
  358.       GC_printf2("Collection %lu reclaimed %ld bytes",
  359.           (unsigned long) GC_gc_no - 1,
  360.              (long)WORDS_TO_BYTES(GC_mem_found));
  361.       GC_printf1(" ---> heapsize = %lu bytes\n",
  362.                   (unsigned long) GC_heapsize);
  363.       /* Printf arguments may be pushed in funny places.  Clear the    */
  364.       /* space.                                */
  365.       GC_printf0("");
  366. #   endif      
  367.  
  368.     /* Check all debugged objects for consistency */
  369.         if (GC_debugging_started) {
  370.             (*GC_check_heap)();
  371.         }
  372.     
  373. #   ifdef PRINTTIMES
  374.     GET_TIME(current_time);
  375.     GC_printf1("World-stopped marking took %lu msecs\n",
  376.                MS_TIME_DIFF(current_time,start_time));
  377. #   endif
  378.     START_WORLD();
  379.     return(TRUE);
  380. }
  381.  
  382.  
  383. /* Finish up a collection.  Assumes lock is held, signals are disabled,    */
  384. /* but the world is otherwise running.                    */
  385. void GC_finish_collection()
  386. {
  387. #   ifdef PRINTTIMES
  388.     CLOCK_TYPE start_time;
  389.     CLOCK_TYPE finalize_time;
  390.     CLOCK_TYPE done_time;
  391.     
  392.     GET_TIME(start_time);
  393.     finalize_time = start_time;
  394. #   endif
  395.  
  396. #   ifdef GATHERSTATS
  397.         GC_mem_found = 0;
  398. #   endif
  399. #   ifdef FIND_LEAK
  400.       /* Mark all objects on the free list.  All objects should be */
  401.       /* marked when we're done.                   */
  402.     {
  403.       register word size;        /* current object size        */
  404.       register ptr_t p;    /* pointer to current object    */
  405.       register struct hblk * h;    /* pointer to block containing *p */
  406.       register hdr * hhdr;
  407.       register int word_no;           /* "index" of *p in *q          */
  408.       int kind;
  409.  
  410.       for (kind = 0; kind < GC_n_kinds; kind++) {
  411.         for (size = 1; size <= MAXOBJSZ; size++) {
  412.           for (p= GC_obj_kinds[kind].ok_freelist[size];
  413.                p != 0; p=obj_link(p)){
  414.         h = HBLKPTR(p);
  415.         hhdr = HDR(h);
  416.         word_no = (((word *)p) - ((word *)h));
  417.         set_mark_bit_from_hdr(hhdr, word_no);
  418.           }
  419.         }
  420.       }
  421.     }
  422.       /* Check that everything is marked */
  423.     GC_start_reclaim(TRUE);
  424. #   else
  425.  
  426.       GC_finalize();
  427. #     ifdef STUBBORN_ALLOC
  428.         GC_clean_changing_list();
  429. #     endif
  430.  
  431. #     ifdef PRINTTIMES
  432.     GET_TIME(finalize_time);
  433. #     endif
  434.  
  435.       /* Clear free list mark bits, in case they got accidentally marked   */
  436.       /* Note: HBLKPTR(p) == pointer to head of block containing *p        */
  437.       /* Also subtract memory remaining from GC_mem_found count.           */
  438.       /* Note that composite objects on free list are cleared.             */
  439.       /* Thus accidentally marking a free list is not a problem;  only     */
  440.       /* objects on the list itself will be marked, and that's fixed here. */
  441.       {
  442.     register word size;        /* current object size        */
  443.     register ptr_t p;    /* pointer to current object    */
  444.     register struct hblk * h;    /* pointer to block containing *p */
  445.     register hdr * hhdr;
  446.     register int word_no;           /* "index" of *p in *q          */
  447.     int kind;
  448.  
  449.     for (kind = 0; kind < GC_n_kinds; kind++) {
  450.       for (size = 1; size <= MAXOBJSZ; size++) {
  451.         for (p= GC_obj_kinds[kind].ok_freelist[size];
  452.              p != 0; p=obj_link(p)){
  453.         h = HBLKPTR(p);
  454.         hhdr = HDR(h);
  455.         word_no = (((word *)p) - ((word *)h));
  456.         clear_mark_bit_from_hdr(hhdr, word_no);
  457. #        ifdef GATHERSTATS
  458.             GC_mem_found -= size;
  459. #        endif
  460.         }
  461.       }
  462.     }
  463.       }
  464.  
  465.  
  466. #     ifdef PRINTSTATS
  467.     GC_printf1("Bytes recovered before sweep - f.l. count = %ld\n",
  468.               (long)WORDS_TO_BYTES(GC_mem_found));
  469. #     endif
  470.  
  471.     /* Reconstruct free lists to contain everything not marked */
  472.       GC_start_reclaim(FALSE);
  473.     
  474. #   endif /* !FIND_LEAK */
  475.  
  476. #   ifdef PRINTSTATS
  477.     GC_printf2(
  478.           "Immediately reclaimed %ld bytes in heap of size %lu bytes\n",
  479.               (long)WORDS_TO_BYTES(GC_mem_found),
  480.               (unsigned long)GC_heapsize);
  481.     GC_printf2("%lu (atomic) + %lu (composite) collectable bytes in use\n",
  482.                (unsigned long)WORDS_TO_BYTES(GC_atomic_in_use),
  483.                (unsigned long)WORDS_TO_BYTES(GC_composite_in_use));
  484. #   endif
  485.  
  486.     /* Reset or increment counters for next cycle */
  487.       GC_words_allocd_before_gc += GC_words_allocd;
  488.       GC_non_gc_bytes_at_gc = GC_non_gc_bytes;
  489.       GC_words_allocd = 0;
  490.       GC_words_wasted = 0;
  491.       GC_mem_freed = 0;
  492.       
  493. #   ifdef PRINTTIMES
  494.     GET_TIME(done_time);
  495.     GC_printf2("Finalize + initiate sweep took %lu + %lu msecs\n",
  496.                MS_TIME_DIFF(finalize_time,start_time),
  497.                MS_TIME_DIFF(done_time,finalize_time));
  498. #   endif
  499. }
  500.  
  501. /* Externally callable routine to invoke full, stop-world collection */
  502. # if defined(__STDC__) || defined(__cplusplus)
  503.     int GC_try_to_collect(GC_stop_func stop_func)
  504. # else
  505.     int GC_try_to_collect(stop_func)
  506.     GC_stop_func stop_func;
  507. # endif
  508. {
  509.     int result;
  510.     DCL_LOCK_STATE;
  511.     
  512.     GC_invoke_finalizers();
  513.     DISABLE_SIGNALS();
  514.     LOCK();
  515.     if (!GC_is_initialized) GC_init_inner();
  516.     /* Minimize junk left in my registers */
  517.       GC_noop(0,0,0,0,0,0);
  518.     result = (int)GC_try_to_collect_inner(stop_func);
  519.     UNLOCK();
  520.     ENABLE_SIGNALS();
  521.     if(result) GC_invoke_finalizers();
  522.     return(result);
  523. }
  524.  
  525. void GC_gcollect(NO_PARAMS)
  526. {
  527.     (void)GC_try_to_collect(GC_never_stop_func);
  528. }
  529.  
  530. word GC_n_heap_sects = 0;    /* Number of sections currently in heap. */
  531.  
  532. /*
  533.  * Use the chunk of memory starting at p of syze bytes as part of the heap.
  534.  * Assumes p is HBLKSIZE aligned, and bytes is a multiple of HBLKSIZE.
  535.  */
  536. void GC_add_to_heap(p, bytes)
  537. struct hblk *p;
  538. word bytes;
  539. {
  540.     word words;
  541.     
  542.     if (GC_n_heap_sects >= MAX_HEAP_SECTS) {
  543.         ABORT("Too many heap sections: Increase MAXHINCR or MAX_HEAP_SECTS");
  544.     }
  545.     if (!GC_install_header(p)) {
  546.         /* This is extremely unlikely. Can't add it.  This will        */
  547.         /* almost certainly result in a    0 return from the allocator,    */
  548.         /* which is entirely appropriate.                */
  549.         return;
  550.     }
  551.     GC_heap_sects[GC_n_heap_sects].hs_start = (ptr_t)p;
  552.     GC_heap_sects[GC_n_heap_sects].hs_bytes = bytes;
  553.     GC_n_heap_sects++;
  554.     words = BYTES_TO_WORDS(bytes - HDR_BYTES);
  555.     HDR(p) -> hb_sz = words;
  556.     GC_freehblk(p);
  557.     GC_heapsize += bytes;
  558.     if ((ptr_t)p <= GC_least_plausible_heap_addr
  559.         || GC_least_plausible_heap_addr == 0) {
  560.         GC_least_plausible_heap_addr = (ptr_t)p - sizeof(word);
  561.             /* Making it a little smaller than necessary prevents    */
  562.             /* us from getting a false hit from the variable    */
  563.             /* itself.  There's some unintentional reflection    */
  564.             /* here.                        */
  565.     }
  566.     if ((ptr_t)p + bytes >= GC_greatest_plausible_heap_addr) {
  567.         GC_greatest_plausible_heap_addr = (ptr_t)p + bytes;
  568.     }
  569. }
  570.  
  571. ptr_t GC_least_plausible_heap_addr = (ptr_t)ONES;
  572. ptr_t GC_greatest_plausible_heap_addr = 0;
  573.  
  574. ptr_t GC_max(x,y)
  575. ptr_t x, y;
  576. {
  577.     return(x > y? x : y);
  578. }
  579.  
  580. ptr_t GC_min(x,y)
  581. ptr_t x, y;
  582. {
  583.     return(x < y? x : y);
  584. }
  585.  
  586. void GC_set_max_heap_size(n)
  587. word n;
  588. {
  589.     GC_max_heapsize = n;
  590. }
  591.  
  592. /*
  593.  * this explicitly increases the size of the heap.  It is used
  594.  * internally, but may also be invoked from GC_expand_hp by the user.
  595.  * The argument is in units of HBLKSIZE.
  596.  * Tiny values of n are rounded up.
  597.  * Returns FALSE on failure.
  598.  */
  599. bool GC_expand_hp_inner(n)
  600. word n;
  601. {
  602.     word bytes;
  603.     struct hblk * space;
  604.     word expansion_slop;    /* Number of bytes by which we expect the */
  605.                     /* heap to expand soon.              */
  606.  
  607.     if (n < MINHINCR) n = MINHINCR;
  608.     bytes = n * HBLKSIZE;
  609.     
  610.     if (GC_max_heapsize != 0 && GC_heapsize + bytes > GC_max_heapsize) {
  611.         /* Exceeded self-imposed limit */
  612.         return(FALSE);
  613.     }
  614.     space = GET_MEM(bytes);
  615.     if( space == 0 ) {
  616.     return(FALSE);
  617.     }
  618. #   ifdef PRINTSTATS
  619.     GC_printf2("Increasing heap size by %lu after %lu allocated bytes\n",
  620.                (unsigned long)bytes,
  621.                (unsigned long)WORDS_TO_BYTES(GC_words_allocd));
  622. #     ifdef UNDEFINED
  623.       GC_printf1("Root size = %lu\n", GC_root_size);
  624.       GC_print_block_list(); GC_print_hblkfreelist();
  625.       GC_printf0("\n");
  626. #    endif
  627. #   endif
  628.     expansion_slop = 8 * WORDS_TO_BYTES(min_words_allocd());
  629.     if (5 * HBLKSIZE * MAXHINCR > expansion_slop) {
  630.         expansion_slop = 5 * HBLKSIZE * MAXHINCR;
  631.     }
  632.     if (GC_last_heap_addr == 0 && !((word)space & SIGNB)
  633.         || GC_last_heap_addr != 0 && GC_last_heap_addr < (ptr_t)space) {
  634.         /* Assume the heap is growing up */
  635.         GC_greatest_plausible_heap_addr =
  636.             GC_max(GC_greatest_plausible_heap_addr,
  637.                    (ptr_t)space + bytes + expansion_slop);
  638.     } else {
  639.         /* Heap is growing down */
  640.         GC_least_plausible_heap_addr =
  641.             GC_min(GC_least_plausible_heap_addr,
  642.                    (ptr_t)space - expansion_slop);
  643.     }
  644.     GC_prev_heap_addr = GC_last_heap_addr;
  645.     GC_last_heap_addr = (ptr_t)space;
  646.     GC_add_to_heap(space, bytes);
  647.     return(TRUE);
  648. }
  649.  
  650. /* Really returns a bool, but it's externally visible, so that's clumsy. */
  651. /* Arguments is in bytes.                        */
  652. int GC_expand_hp(bytes)
  653. size_t bytes;
  654. {
  655.     int result;
  656.     DCL_LOCK_STATE;
  657.     
  658.     DISABLE_SIGNALS();
  659.     LOCK();
  660.     if (!GC_is_initialized) GC_init_inner();
  661.     result = (int)GC_expand_hp_inner(divHBLKSZ((word)bytes));
  662.     UNLOCK();
  663.     ENABLE_SIGNALS();
  664.     return(result);
  665. }
  666.  
  667. bool GC_collect_or_expand(needed_blocks)
  668. word needed_blocks;
  669. {
  670.     static int count = 0;  /* How many failures? */
  671.     
  672.     if (!GC_incremental && !GC_dont_gc && GC_should_collect()) {
  673.       GC_gcollect_inner();
  674.     } else {
  675.       word blocks_to_get = GC_heapsize/(HBLKSIZE*GC_free_space_divisor)
  676.                      + needed_blocks;
  677.       
  678.       if (blocks_to_get > MAXHINCR) {
  679.           if (needed_blocks > MAXHINCR) {
  680.               blocks_to_get = needed_blocks;
  681.           } else {
  682.               blocks_to_get = MAXHINCR;
  683.           }
  684.       }
  685.       if (!GC_expand_hp_inner(blocks_to_get)
  686.         && !GC_expand_hp_inner(needed_blocks)) {
  687.           if (count++ < 10) {
  688.               WARN("Out of Memory!  Trying to continue ...\n", 0);
  689.         GC_gcollect_inner();
  690.     } else {
  691.         WARN("Out of Memory!  Returning NIL!\n", 0);
  692.         return(FALSE);
  693.     }
  694.       } else if (count) {
  695. #      ifdef PRINTSTATS
  696.         GC_printf0("Memory available again ...\n");
  697. #      endif
  698.           count = 0;
  699.       }
  700.     }
  701.     return(TRUE);
  702. }
  703.  
  704. /*
  705.  * Make sure the object free list for sz is not empty.
  706.  * Return a pointer to the first object on the free list.
  707.  * The object MUST BE REMOVED FROM THE FREE LIST BY THE CALLER.
  708.  * Assumes we hold the allocator lock and signals are disabled.
  709.  *
  710.  */
  711. ptr_t GC_allocobj(sz, kind)
  712. word sz;
  713. int kind;
  714. {
  715.     register ptr_t * flh = &(GC_obj_kinds[kind].ok_freelist[sz]);
  716.     
  717.     if (sz == 0) return(0);
  718.  
  719.     while (*flh == 0) {
  720.       /* Do our share of marking work */
  721.         if(GC_incremental && !GC_dont_gc) GC_collect_a_little_inner(1);
  722.       /* Sweep blocks for objects of this size */
  723.           GC_continue_reclaim(sz, kind);
  724.       if (*flh == 0) {
  725.         GC_new_hblk(sz, kind);
  726.       }
  727.       if (*flh == 0) {
  728.         if (!GC_collect_or_expand((word)1)) return(0);
  729.       }
  730.     }
  731.     
  732.     return(*flh);
  733. }
  734.